package hzk.codex2016.list;

public class LinkedList_insSort {

	/**
	 * https://leetcode.com/problems/insertion-sort-list/
	 * @param head
	 * @return
	 */
	public ListNode insertionSortList(ListNode head) {
		ListNode fakeHead=new ListNode(0),p=head,q;
		while (p!=null){
			q=p.next;
			
			//calc r: pos to insert for p
			ListNode rpre=fakeHead,r=rpre.next;
			while (r!=null && r.val<p.val) {
				rpre=r;
				r=r.next;
			}
			
			//insert p between rpre and r
			rpre.next=p;
			p.next=r;
		 
			p=q;
		}
		
		
		return fakeHead.next;
        
    }
	
	public static void main(String[] args){
		LinkedList_insSort s=new LinkedList_insSort();
		System.out.println(s.insertionSortList(Lists.sll()));
		System.out.println(s.insertionSortList(Lists.sll(3)));
		System.out.println(s.insertionSortList(Lists.sll(3,7)));
		System.out.println(s.insertionSortList(Lists.sll(5,3)));
		System.out.println(s.insertionSortList(Lists.sll(6,45,13,24,7,1,2,18,9,6,3,10)));
		
	}
}
